//===--- StringExtras.cpp - String Utilities ------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
//
// This file implements utilities for working with words and camelCase
// names.
//
//===----------------------------------------------------------------------===//

#include "polarphp/basic/StringExtras.h"
#include "clang/Basic/CharInfo.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/SmallString.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringSwitch.h"
#include "llvm/Support/Compiler.h"
#include <algorithm>

namespace polar {

using namespace camel_case;

bool canBeArgumentLabel(StringRef identifier) {
   return llvm::StringSwitch<bool>(identifier)
      .Case("inout", false)
      .Case("$", false)
      .Default(true);
}

bool canBeMemberName(StringRef identifier) {
   return llvm::StringSwitch<bool>(identifier)
      .Case("init", false)
      .Case("Interface", false)
      .Case("self", false)
      .Case("Type", false)
      .Default(true);
}

bool isPreposition(StringRef word) {
#define PREPOSITION(Word)                       \
  if (word.equals_lower(#Word))                 \
    return true;

#include "polarphp/basic/internal/PartsOfSpeechDef.h"

   return false;
}

PartOfSpeech getPartOfSpeech(StringRef word) {
   // FIXME: This implementation is woefully inefficient.
#define PREPOSITION(Word)                       \
  if (word.equals_lower(#Word))                 \
    return PartOfSpeech::Preposition;
#define VERB(Word)                              \
  if (word.equals_lower(#Word))                 \
    return PartOfSpeech::Verb;

#include "polarphp/basic/internal/PartsOfSpeechDef.h"

   // Identify gerunds, which always end in "ing".
   if (word.endswith("ing") && word.size() > 4) {
      StringRef possibleVerb = word.drop_back(3);

      // If what remains is a verb, we have a gerund.
      if (getPartOfSpeech(possibleVerb) == PartOfSpeech::Verb)
         return PartOfSpeech::Gerund;

      // Try adding an "e" and look for that as a verb.
      if (possibleVerb.back() != 'e') {
         SmallString<16> possibleVerbWithE;
         possibleVerbWithE += possibleVerb;
         possibleVerbWithE += 'e';
         if (getPartOfSpeech(possibleVerbWithE) == PartOfSpeech::Verb)
            return PartOfSpeech::Gerund;
      }

      // If there is a repeated letter at the back, drop that second
      // instance of that letter and try again.
      unsigned count = possibleVerb.size();
      if (possibleVerb[count - 1] == possibleVerb[count - 2] &&
          getPartOfSpeech(possibleVerb.drop_back()) == PartOfSpeech::Verb)
         return PartOfSpeech::Gerund;
   }

   // "auto" tends to be used as a verb prefix.
   if (startsWithIgnoreFirstCase(word, "auto") && word.size() > 4) {
      if (getPartOfSpeech(word.substr(4)) == PartOfSpeech::Verb)
         return PartOfSpeech::Verb;
   }

   // "re" can prefix a verb.
   if (startsWithIgnoreFirstCase(word, "re") && word.size() > 2) {
      if (getPartOfSpeech(word.substr(2)) == PartOfSpeech::Verb)
         return PartOfSpeech::Verb;
   }

   // "de" can prefix a verb.
   if (startsWithIgnoreFirstCase(word, "de") && word.size() > 2) {
      if (getPartOfSpeech(word.substr(2)) == PartOfSpeech::Verb)
         return PartOfSpeech::Verb;
   }

   return PartOfSpeech::Unknown;
}

/// Whether the given word is a plural s
static bool isPluralSuffix(StringRef word) {
   return word == "s" || word == "es" || word == "ies";
}

namespace camel_case {

void WordIterator::computeNextPosition() const {
   assert(Position < String.size() && "Already at end of string");

   unsigned i = Position, n = String.size();

   // Treat _ as a word on its own. Don't coalesce.
   if (String[i] == '_') {
      NextPosition = i + 1;
      NextPositionValid = true;
      return;
   }

   // Skip over any uppercase letters at the beginning of the word.
   while (i < n && clang::isUppercase(String[i]))
      ++i;

   // If there was more than one uppercase letter, this is an
   // acronym.
   if (i - Position > 1) {
      // If we hit the end of the string, that's it. Otherwise, this
      // word ends before the last uppercase letter if the next word is alphabetic
      // (URL_Loader) or after the last uppercase letter if it's not (UTF_8).

      // Collect the lowercase letters up to the next word.
      unsigned endOfNext = i;
      while (endOfNext < n && clang::isLowercase(String[endOfNext]))
         ++endOfNext;

      // If the next word is a plural suffix, add it on.
      if (i == n ||
          (isPluralSuffix(String.slice(i, endOfNext)) &&
           String.slice(i - 1, endOfNext) != "Is"))
         NextPosition = endOfNext;
      else if (clang::isLowercase(String[i]))
         NextPosition = i - 1;
      else
         NextPosition = i;

      NextPositionValid = true;
      return;
   }

   // Skip non-uppercase letters.
   while (i < n && !clang::isUppercase(String[i]) && String[i] != '_')
      ++i;

   NextPosition = i;
   NextPositionValid = true;
}

void WordIterator::computePrevPosition() const {
   assert(Position > 0 && "Already at beginning of string");

   unsigned i = Position;

   // While we see non-uppercase letters, keep moving back.
   while (i > 0 && !clang::isUppercase(String[i - 1]) && String[i - 1] != '_')
      --i;

   // If what we found is a plural suffix, keep going.
   unsigned effectiveEndPosition = Position;
   if (i > 0 && isPluralSuffix(String.slice(i, Position))) {
      effectiveEndPosition = i;
      while (i > 0 && !clang::isUppercase(String[i - 1]) && String[i - 1] != '_')
         --i;
   }

   // If we found any lowercase letters, this was a normal camel case
   // word (not an acronym).
   if (i < effectiveEndPosition) {
      // If we hit the beginning of the string, that's it. Otherwise, this
      // word starts with an uppercase letter if the next word is alphabetic
      // (URL_Loader) or after the last uppercase letter if it's not (UTF_8).
      PrevPosition = i;
      if (i != 0 && clang::isLowercase(String[i]) && String[i - 1] != '_')
         --PrevPosition;
      PrevPositionValid = true;
      return;
   }

   // Treat _ as a word on its own. Don't coalesce.
   if (String[i - 1] == '_') {
      PrevPosition = i - 1;
      PrevPositionValid = true;
      return;
   }

   // There were no lowercase letters, so this is an acronym. Keep
   // skipping uppercase letters.
   while (i > 0 && clang::isUppercase(String[i - 1]))
      --i;

   PrevPosition = i;
   PrevPositionValid = true;
}

StringRef getFirstWord(StringRef string) {
   if (string.empty())
      return "";

   return *WordIterator(string, 0);
}

StringRef getLastWord(StringRef string) {
   if (string.empty())
      return "";

   return *--WordIterator(string, string.size());
}

bool sameWordIgnoreFirstCase(StringRef word1, StringRef word2) {
   if (word1.size() != word2.size())
      return false;

   if (clang::toLowercase(word1[0]) != clang::toLowercase(word2[0]))
      return false;

   return word1.substr(1) == word2.substr(1);
}

bool startsWithIgnoreFirstCase(StringRef word1, StringRef word2) {
   if (word1.size() < word2.size())
      return false;

   if (clang::toLowercase(word1[0]) != clang::toLowercase(word2[0]))
      return false;

   return word1.substr(1, word2.size() - 1) == word2.substr(1);
}

StringRef toLowercaseWord(StringRef string,
                          SmallVectorImpl<char> &scratch) {
   if (string.empty())
      return string;

   // Already lowercase.
   if (!clang::isUppercase(string[0]))
      return string;

   // Acronym doesn't get lowercased.
   if (string.size() > 1 && clang::isUppercase(string[1]))
      return string;

   // Lowercase the first letter, append the rest.
   scratch.clear();
   scratch.push_back(clang::toLowercase(string[0]));
   scratch.append(string.begin() + 1, string.end());
   return StringRef(scratch.data(), scratch.size());
}

StringRef toSentencecase(StringRef string,
                         SmallVectorImpl<char> &scratch) {
   if (string.empty())
      return string;

   // Can't be uppercased.
   if (!clang::isLowercase(string[0]))
      return string;

   // Uppercase the first letter, append the rest.
   scratch.clear();
   scratch.push_back(clang::toUppercase(string[0]));
   scratch.append(string.begin() + 1, string.end());
   return StringRef(scratch.data(), scratch.size());
}

StringRef dropPrefix(StringRef string) {

   unsigned firstLower = 0, n = string.size();

   if (n < 4)
      return string;

   for (; firstLower < n; ++firstLower) {
      if (!clang::isUppercase(string[firstLower]))
         break;
   }

   if (firstLower == n)
      return string;

   if (firstLower >= 3 && firstLower <= 4)
      return string.substr(firstLower - 1);

   return string;
}

StringRef appendSentenceCase(SmallVectorImpl<char> &buffer,
                             StringRef string) {
   // Trivial case: empty string.
   if (string.empty())
      return StringRef(buffer.data(), buffer.size());

   // Uppercase the first letter, append the rest.
   buffer.push_back(clang::toUppercase(string[0]));
   buffer.append(string.begin() + 1, string.end());
   return StringRef(buffer.data(), buffer.size());
}

size_t findWord(StringRef string, StringRef word) {
   assert(!word.empty());
   assert(clang::isUppercase(word[0]));

   // Scan forward until we find the word as a complete word.
   size_t startingIndex = 0;
   while (true) {
      size_t index = string.find(word, startingIndex);
      if (index == StringRef::npos)
         return StringRef::npos;

      // If any of the following checks fail, we want to start searching
      // past the end of the match.  (This assumes that the word doesn't
      // end with a prefix of itself, e.g. "LikableLike".)
      startingIndex = index + word.size();

      // We assume that we don't have to check if the match starts a new
      // word in the string.

      // If we find the word, check whether it's a valid match.
      StringRef suffix = string.substr(index);
      if (!suffix.empty() && clang::isLowercase(suffix[0]))
         continue;

      return index;
   }
}

/// Skip a type suffix that can be dropped.
static Optional<StringRef> skipTypeSuffix(StringRef typeName) {
   if (typeName.empty()) return None;

   auto lastWord = getLastWord(typeName);

   // "Type" suffix.
   if (lastWord == "Type" && typeName.size() > 4) {
      return typeName.drop_back(4);
   }

   // "Ref" suffix.
   if (lastWord == "Ref" && typeName.size() > 3) {
      return typeName.drop_back(3);
   }

   // "Mask" suffix.
   if (lastWord == "Mask" && typeName.size() > 4) {
      return typeName.drop_back(4);
   }

   // \d+D for dimensionality.
   if (typeName.back() == 'D' && typeName.size() > 1) {
      unsigned firstDigit = typeName.size() - 1;
      while (firstDigit > 0) {
         if (!isdigit(typeName[firstDigit - 1])) break;
         --firstDigit;
      }

      if (firstDigit < typeName.size() - 1) {
         return typeName.substr(0, firstDigit);
      }
   }

   // _t.
   if (typeName.size() > 2 && typeName.endswith("_t")) {
      return typeName.drop_back(2);
   }
   return None;
}

/// Match a word within a name to a word within a type.
static bool matchNameWordToTypeWord(StringRef nameWord, StringRef typeWord) {
   // If the name word is longer, there's no match.
   if (nameWord.size() > typeWord.size()) return false;

   // If the name word is shorter, try for a partial match.
   if (nameWord.size() < typeWord.size()) {
      // We can match the suffix of the type so long as everything preceding the
      // match is neither a lowercase letter nor a '_'. This ignores type
      // prefixes for acronyms, e.g., the 'NS' in 'NSURL'.
      if (typeWord.endswith_lower(nameWord) &&
          !clang::isLowercase(typeWord[typeWord.size() - nameWord.size()])) {
         // Check that everything preceding the match is neither a lowercase letter
         // nor a '_'.
         for (unsigned i = 0, n = nameWord.size(); i != n; ++i) {
            if (clang::isLowercase(typeWord[i]) || typeWord[i] == '_') return false;
         }

         return true;
      }

      // We can match a prefix so long as everything following the match is
      // a number.
      if (typeWord.startswith_lower(nameWord)) {
         for (unsigned i = nameWord.size(), n = typeWord.size(); i != n; ++i) {
            if (!clang::isDigit(typeWord[i])) return false;
         }

         return true;
      }

      return false;
   }

   // Check for an exact match.
   return nameWord.equals_lower(typeWord);
}
} // camel_case

/// Match the beginning of the name to the given type name.
StringRef matchLeadingTypeName(StringRef name,
                               OmissionTypeName typeName) {
   // Match the camelCase beginning of the name to the
   // ending of the type name.
   auto nameWords = getWords(name);
   auto typeWords = getWords(typeName.Name);
   auto nameWordIter = nameWords.begin(),
      nameWordIterEnd = nameWords.end();
   auto typeWordRevIter = typeWords.rbegin(),
      typeWordRevIterEnd = typeWords.rend();

   // Find the last instance of the first word in the name within
   // the words in the type name.
   typeWordRevIter = std::find_if(typeWordRevIter, typeWordRevIterEnd,
                                  [nameWordIter](StringRef word) {
                                     return matchNameWordToTypeWord(*nameWordIter, word);
                                  });

   // If we didn't find the first word in the name at all, we're
   // done.
   if (typeWordRevIter == typeWordRevIterEnd)
      return name;

   // Now, match from the first word up until the end of the type name.
   auto typeWordIter = typeWordRevIter.base(),
      typeWordIterEnd = typeWords.end();
   ++nameWordIter;

   // FIXME: Use std::mismatch once we update to C++14.
   while (typeWordIter != typeWordIterEnd &&
          nameWordIter != nameWordIterEnd &&
          matchNameWordToTypeWord(*nameWordIter, *typeWordIter)) {
      ++typeWordIter;
      ++nameWordIter;
   }

   // If we didn't reach the end of the type name, don't match.
   if (typeWordIter != typeWordIterEnd)
      return name;

   // Chop of the beginning of the name.
   return nameWordIter.getRestOfStr();
}

StringRef StringScratchSpace::copyString(StringRef string) {
   void *memory = Allocator.Allocate(string.size(), alignof(char));
   memcpy(memory, string.data(), string.size());
   return StringRef(static_cast<char *>(memory), string.size());
}

void InheritedNameSet::add(StringRef name) {
   Names.insert(name);
}

bool InheritedNameSet::contains(StringRef name) const {
   auto set = this;
   do {
      if (set->Names.count(name) > 0) return true;
      set = set->Parent;
   } while (set);

   return false;
}

/// Wrapper for toLowercaseWord that uses string scratch space.
StringRef toLowercaseWord(StringRef string,
                          StringScratchSpace &scratch) {
   llvm::SmallString<32> scratchStr;
   StringRef result = toLowercaseWord(string, scratchStr);
   if (string == result)
      return string;

   return scratch.copyString(result);
}

/// Omit needless words from the beginning of a name.
static StringRef omitNeedlessWordsFromPrefix(StringRef name,
                                             OmissionTypeName type) {
   if (type.empty())
      return name;

   // Match the result type to the beginning of the name.
   StringRef newName = matchLeadingTypeName(name, type);
   if (newName == name)
      return name;

   auto firstWord = getFirstWord(newName);

   // If we have a preposition, we can chop off type information at the
   // beginning of the name.
   if (getPartOfSpeech(firstWord) == PartOfSpeech::Preposition &&
       newName.size() > firstWord.size()) {
      // If the preposition was "by" and is followed by a gerund, also remove
      // "by".
      if (firstWord == "By") {
         StringRef nextWord = getFirstWord(
            newName.substr(firstWord.size()));
         if (nextWord.endswith("ing")) {
            return newName.substr(firstWord.size());
         }
      }

      return newName;
   }

   return name;
}

/// Identify certain vacuous names to which we do not want to reduce any name.
static bool isVacuousName(StringRef name) {
   return sameWordIgnoreFirstCase(name, "get") ||
          sameWordIgnoreFirstCase(name, "for") ||
          sameWordIgnoreFirstCase(name, "set") ||
          sameWordIgnoreFirstCase(name, "using") ||
          sameWordIgnoreFirstCase(name, "with");
}

/// Determine whether the given text matches a property name.
static bool textMatchesPropertyName(StringRef text,
                                    const InheritedNameSet *allPropertyNames) {
   if (!allPropertyNames) return false;

   SmallString<16> localScratch;
   auto name = toLowercaseWord(text, localScratch);

   // A property with exactly this name.
   if (allPropertyNames->contains(name)) return true;

   // From here on, we'll be working with scratch space.
   if (name.data() != localScratch.data())
      localScratch = name;

   if (localScratch.back() == 'y') {
      // If the last letter is a 'y', try 'ies'.
      localScratch.pop_back();
      localScratch += "ies";
      if (allPropertyNames->contains(localScratch)) return true;
   } else {
      // Otherwise, add an 's' and try again.
      localScratch += 's';
      if (allPropertyNames->contains(localScratch)) return true;

      // Alternatively, try to add 'es'.
      localScratch.pop_back();
      localScratch += "es";
      if (allPropertyNames->contains(localScratch)) return true;
   }

   return false;
}

namespace {
/// Describes the role that a particular name has within a
/// signature, which can affect how we omit needless words.
enum class NameRole {
   /// The base name of a function or method.
      BaseName,

   /// The first parameter of a function or method.
      FirstParameter,

   // Subsequent parameters in a function or method.
      SubsequentParameter,

   // The name of a property.
      Property,

   // A partial name; used internally.
      Partial,
};
} // end anonymous namespace

static StringRef
omitTrailingTypeNameWithSpecialCases(StringRef name,
                                     OmissionTypeName typeName,
                                     NameRole role,
                                     const InheritedNameSet *allPropertyNames);

/// Returns the iterator pointing to the first word in \p name that starts the
/// match for \p typeName (anchored at the end of \p name).
///
/// If there is no match, returns the end WordIterator for \p name.
static Words::iterator matchTypeNameFromBackWithSpecialCases(
   StringRef name, OmissionTypeName typeName,
   const InheritedNameSet *allPropertyNames) {
   // Get the camel-case words in the name and type name.
   auto nameWords = getWords(name);
   auto typeWords = getWords(typeName.Name);

   // Match the last words in the type name to the last words in the
   // name.
   auto nameWordRevIter = nameWords.rbegin(),
      nameWordRevIterBegin = nameWordRevIter,
      nameWordRevIterEnd = nameWords.rend();
   auto typeWordRevIter = typeWords.rbegin(),
      typeWordRevIterEnd = typeWords.rend();

   while (nameWordRevIter != nameWordRevIterEnd &&
          typeWordRevIter != typeWordRevIterEnd) {
      // If the names match, continue.
      auto nameWord = *nameWordRevIter;
      if (matchNameWordToTypeWord(nameWord, *typeWordRevIter)) {
         ++nameWordRevIter;
         ++typeWordRevIter;
         continue;
      }

      // Special case: "Indexes" and "Indices" in the name match
      // "IndexSet" in the type.
      if ((matchNameWordToTypeWord(nameWord, "Indexes") ||
           matchNameWordToTypeWord(nameWord, "Indices")) &&
          *typeWordRevIter == "Set") {
         auto nextTypeWordRevIter = typeWordRevIter;
         ++nextTypeWordRevIter;
         if (nextTypeWordRevIter != typeWordRevIterEnd &&
             matchNameWordToTypeWord("Index", *nextTypeWordRevIter)) {
            ++nameWordRevIter;
            typeWordRevIter = nextTypeWordRevIter;
            ++typeWordRevIter;
            continue;
         }
      }

      // Special case: "Index" in the name matches "Int" or "Integer" in the type.
      if (matchNameWordToTypeWord(nameWord, "Index") &&
          (matchNameWordToTypeWord("Int", *typeWordRevIter) ||
           matchNameWordToTypeWord("Integer", *typeWordRevIter))) {
         ++nameWordRevIter;
         ++typeWordRevIter;
         continue;
      }

      // Special case: "ObjectValue" in the name matches "Object" in the
      // type.
      if (matchNameWordToTypeWord("Object", *typeWordRevIter) &&
          matchNameWordToTypeWord(nameWord, "Value")) {
         auto nextNameWordRevIter = std::next(nameWordRevIter);
         if (nextNameWordRevIter != nameWordRevIterEnd &&
             matchNameWordToTypeWord(*nextNameWordRevIter, "Object")) {
            nameWordRevIter = nextNameWordRevIter;
            ++nameWordRevIter;
            ++typeWordRevIter;
            continue;
         }
      }

      // Special case: if the word in the name ends in 's', and we have
      // a collection element type, see if this is a plural.
      if (!typeName.CollectionElement.empty() && nameWord.size() > 2 &&
          nameWord.back() == 's') {
         // Check <element name>s.
         auto shortenedNameWord = nameWordRevIter.base().getPriorStr().drop_back();
         auto newShortenedNameWord = omitTrailingTypeNameWithSpecialCases(
            shortenedNameWord, typeName.CollectionElement, NameRole::Partial,
            allPropertyNames);

         if (shortenedNameWord != newShortenedNameWord) {
            unsigned targetSize = newShortenedNameWord.size();
            auto newIter = llvm::make_reverse_iterator(WordIterator(name,
                                                                    targetSize));
#ifndef NDEBUG
            while (nameWordRevIter.base().getPosition() > targetSize)
               ++nameWordRevIter;
            assert(nameWordRevIter == newIter);
#else
            nameWordRevIter = newIter;
#endif
            continue;
         }
      }

      // If this is a skippable suffix, skip it and keep looking.
      if (nameWordRevIter == nameWordRevIterBegin) {
         if (auto withoutSuffix = skipTypeSuffix(typeName.Name)) {
            typeName.Name = *withoutSuffix;
            typeWords = getWords(typeName.Name);
            typeWordRevIter = typeWords.rbegin();
            typeWordRevIterEnd = typeWords.rend();
            continue;
         }
      }

      break;
   }

   return nameWordRevIter.base();
}

static StringRef
omitSelfTypeFromBaseName(StringRef name, OmissionTypeName typeName,
                         const InheritedNameSet *allPropertyNames,
                         StringScratchSpace &scratch) {
   // If we have no name or no type name, there is nothing to do.
   if (name.empty() || typeName.empty()) return name;

   // Deliberately drop the collection element from typeName.
   typeName.CollectionElement = StringRef();

   auto nameWords = getWords(name);
   Optional<llvm::iterator_range<WordIterator>> matchingRange;

   // Search backwards for the type name, whether anchored at the end or not.
   for (auto nameReverseIter = nameWords.rbegin();
        nameReverseIter != nameWords.rend();
        ++nameReverseIter) {
      StringRef matchName = nameReverseIter.base().getPriorStr();
      auto matchIter = matchTypeNameFromBackWithSpecialCases(matchName, typeName,
                                                             allPropertyNames);
      auto matchIterInFullName = WordIterator(name, matchIter.getPosition());
      if (matchIterInFullName != nameReverseIter.base()) {
         matchingRange = llvm::make_range(matchIterInFullName,
                                          nameReverseIter.base());
         break;
      }

      // Note: This behavior fell out of a previous implementation of
      // omit-needless-words, even though it probably wasn't intentional. At this
      // point, though, it could be source-breaking to change it.
      while (auto withoutSuffix = skipTypeSuffix(typeName.Name))
         typeName.Name = *withoutSuffix;
   }

   // If we matched nothing, or if the type name was all the way at the start
   // of the base name, don't strip anything.
   if (!matchingRange || matchingRange->begin() == nameWords.begin())
      return name;
   assert(matchingRange->begin() != matchingRange->end() &&
          "should not have been considered a match");

   // Don't strip just "Error" at the end of a base name.
   // FIXME: Is this still relevant?
   if (matchingRange->end() == nameWords.end() &&
       std::next(matchingRange->begin()) == nameWords.end() &&
       *matchingRange->begin() == "Error") {
      return name;
   }

   // Only strip a type name that follows a verb.
   switch (getPartOfSpeech(*std::prev(matchingRange->begin()))) {
      case PartOfSpeech::Verb:
         break;
      case PartOfSpeech::Preposition:
      case PartOfSpeech::Gerund:
      case PartOfSpeech::Unknown:
         return name;
   }

   // Splice together the parts before and after the matched
   // type. For example, if we matched "ViewController" in
   // "dismissViewControllerAnimated", stitch together
   // "dismissAnimated".

   // Don't prune redundant type information from the base name if
   // there is a corresponding property (either singular or plural).
   StringRef removedText = name.substr(matchingRange->begin().getPosition(),
                                       matchingRange->end().getPosition());
   if (textMatchesPropertyName(removedText, allPropertyNames))
      return name;

   SmallString<16> newName = matchingRange->begin().getPriorStr();
   newName += matchingRange->end().getRestOfStr();

   // If we ended up with something that can't be a member name, do nothing.
   if (!canBeMemberName(newName))
      return name;

   // If we ended up with a vacuous name like "get" or "set", do nothing.
   if (isVacuousName(newName))
      return name;

   // We're done.
   return scratch.copyString(newName);
}

static StringRef
omitTrailingTypeNameWithSpecialCases(StringRef name, OmissionTypeName typeName,
                                     NameRole role,
                                     const InheritedNameSet *allPropertyNames) {
   // If we have no name or no type name, there is nothing to do.
   if (name.empty() || typeName.empty()) return name;

   auto nameWords = getWords(name);
   Words::iterator matchIter =
      matchTypeNameFromBackWithSpecialCases(name, typeName, allPropertyNames);

   if (matchIter == nameWords.end())
      return name;

   // Handle complete name matches.
   if (matchIter == nameWords.begin()) {
      // If we're doing a partial match or we have an initial
      // parameter, return the empty string.
      if (role == NameRole::Partial || role == NameRole::FirstParameter)
         return "";

      // Leave the name alone.
      return name;
   }

   // Don't strip just "Error".
   if (std::next(matchIter) == nameWords.end() && *matchIter == "Error")
      return name;

   switch (role) {
      case NameRole::Property:
         // Always strip off type information.
         break;

      case NameRole::FirstParameter:
      case NameRole::Partial:
      case NameRole::SubsequentParameter: {
         // Classify the part of speech of the word before the type information we
         // would strip off. We only want to strip it if the previous word is a
         // preposition, verb, or gerund.
         auto previousWordIter = std::prev(matchIter);
         if (getPartOfSpeech(*previousWordIter) == PartOfSpeech::Unknown)
            return name;
         break;
      }

      case NameRole::BaseName: {
         // Classify the part of speech of the word before the type
         // information we would strip off.
         auto previousWordIter = std::prev(matchIter);
         switch (getPartOfSpeech(*previousWordIter)) {
            case PartOfSpeech::Preposition:
               // If there's nothing preceding the preposition, don't strip anything.
               if (previousWordIter == nameWords.begin())
                  return name;
               break;

            case PartOfSpeech::Verb:
            case PartOfSpeech::Gerund:
               // Don't prune redundant type information from the base name if
               // there is a corresponding property (either singular or plural).
               if (textMatchesPropertyName(matchIter.getRestOfStr(), allPropertyNames))
                  return name;
               break;

            case PartOfSpeech::Unknown:
               // Assume it's a noun or adjective; don't strip anything.
               return name;
         }

         break;
      }
   }

   // Strip off the part of the name that is redundant with
   // type information.
   StringRef newName = matchIter.getPriorStr();

   switch (role) {
      case NameRole::BaseName:
      case NameRole::Property:
         // If we ended up with something that can't be a member name, do nothing.
         if (!canBeMemberName(newName))
            return name;

         // If we ended up with a vacuous name like "get" or "set", do nothing.
         if (isVacuousName(newName))
            return name;

         break;

      case NameRole::SubsequentParameter:
      case NameRole::FirstParameter:
      case NameRole::Partial:
         break;
   }

   // We're done.
   return newName;
}

StringRef camel_case::toLowercaseInitialisms(StringRef string,
                                 StringScratchSpace &scratch) {
   llvm::SmallString<32> scratchStr;
   StringRef result = toLowercaseInitialisms(string, scratchStr);
   if (string == result)
      return string;
   return scratch.copyString(result);
}

StringRef
camel_case::toLowercaseInitialisms(StringRef string,
                       SmallVectorImpl<char> &scratch) {

   if (string.empty())
      return string;

   // Already lowercase.
   if (!clang::isUppercase(string[0]))
      return string;

   // Lowercase until we hit the an uppercase letter followed by a
   // non-uppercase letter.
   scratch.clear();
   scratch.reserve(string.size());
   for (unsigned i = 0, n = string.size(); i != n; ++i) {
      // If the next character is not uppercase, stop.
      if (i < n - 1 && !clang::isUppercase(string[i + 1])) {
         // If the next non-uppercase character was not a letter, we seem
         // to have a plural, or we're at the beginning, we should still
         // lowercase the character we're on.
         if (i == 0 || !clang::isLetter(string[i + 1]) ||
             isPluralSuffix(getFirstWord(string.substr(i + 1)))) {
            scratch.push_back(clang::toLowercase(string[i]));
            ++i;
         }

         scratch.append(string.substr(i).begin(), string.substr(i).end());
         break;
      }

      scratch.push_back(clang::toLowercase(string[i]));
   }

   return {scratch.data(), scratch.size()};
}

/// Determine whether the given word occurring before the given
/// preposition results in a conflict that suppresses preposition
/// splitting.
static bool wordConflictsBeforePreposition(StringRef word,
                                           StringRef preposition) {
   if (sameWordIgnoreFirstCase(preposition, "in") &&
       sameWordIgnoreFirstCase(word, "plug"))
      return true;

   return false;
}

/// Determine whether the given word occurring after the given
/// preposition results in a conflict that suppresses preposition
/// splitting.
static bool wordConflictsAfterPreposition(StringRef word,
                                          StringRef preposition) {
   if (sameWordIgnoreFirstCase(preposition, "with")) {
      if (sameWordIgnoreFirstCase(word, "error") ||
          sameWordIgnoreFirstCase(word, "no"))
         return true;
   }

   if (sameWordIgnoreFirstCase(preposition, "to")) {
      if (sameWordIgnoreFirstCase(word, "visible") ||
          sameWordIgnoreFirstCase(word, "backing"))
         return true;
   }

   if (sameWordIgnoreFirstCase(preposition, "from")) {
      if (sameWordIgnoreFirstCase(word, "backing"))
         return true;
   }

   return false;
}

/// When splitting based on a preposition, whether we should place the
/// preposition on the argument label (vs. on the base name).
static bool shouldPlacePrepositionOnArgLabel(StringRef beforePreposition,
                                             StringRef preposition,
                                             StringRef afterPreposition) {
   // X/Y/Z often used as coordinates and should be the labels.
   if (afterPreposition == "X" ||
       afterPreposition == "Y" ||
       afterPreposition == "Z")
      return false;

   return true;
}

/// Determine whether the word preceding the preposition is part of an
/// "extended" preposition, such as "compatible with".
static bool priorWordExtendsPreposition(StringRef preceding,
                                        StringRef preposition) {
   // compatible with
   if (sameWordIgnoreFirstCase(preceding, "compatible") &&
       sameWordIgnoreFirstCase(preposition, "with"))
      return true;

   // best matching
   if (sameWordIgnoreFirstCase(preceding, "best") &&
       sameWordIgnoreFirstCase(preposition, "matching"))
      return true;

   // according to
   if (sameWordIgnoreFirstCase(preceding, "according") &&
       sameWordIgnoreFirstCase(preposition, "to"))
      return true;

   // bound by
   if (sameWordIgnoreFirstCase(preceding, "bound") &&
       sameWordIgnoreFirstCase(preposition, "by"))
      return true;

   // separated by
   if (sameWordIgnoreFirstCase(preceding, "separated") &&
       sameWordIgnoreFirstCase(preposition, "by"))
      return true;

   return false;
}

/// Determine whether the preposition in a split is "vacuous", and
/// should be removed.
static bool isVacuousPreposition(StringRef beforePreposition,
                                 StringRef preposition,
                                 StringRef afterPreposition,
                                 const OmissionTypeName &paramType) {
   // Only consider "with" or "using" to be potentially vacuous.
   if (!sameWordIgnoreFirstCase(preposition, "with") &&
       !sameWordIgnoreFirstCase(preposition, "using"))
      return false;

   // If the preposition is "with" followed by "zone", never consider
   // it vacuous.
   if (sameWordIgnoreFirstCase(preposition, "with") &&
       sameWordIgnoreFirstCase(
          getFirstWord(afterPreposition), "zone"))
      return false;

   // If the parameter has a default argument, it's vacuous.
   if (paramType.hasDefaultArgument()) return true;

   // If the parameter is of function type, it's vacuous.
   if (paramType.isFunction()) return true;

   return false;
}

namespace {
using ReverseWordIterator = std::reverse_iterator<WordIterator>;
} // end anonymous namespace

/// Find the last preposition in the given word.
static ReverseWordIterator findLastPreposition(ReverseWordIterator first,
                                               ReverseWordIterator last,
                                               bool recursive = false) {
   // Find the last preposition.
   auto result =
      std::find_if(first, last,
                   [](StringRef word) {
                      return getPartOfSpeech(word) == PartOfSpeech::Preposition;
                   });

   // If the preposition is "of", look for a previous preposition.
   if (!recursive && result != last &&
       sameWordIgnoreFirstCase(*result, "of")) {
      auto prevPreposition = findLastPreposition(std::next(result), last,
         /*recursive=*/true);
      if (prevPreposition != last &&
          !sameWordIgnoreFirstCase(*prevPreposition, "of") &&
          !sameWordIgnoreFirstCase(*prevPreposition, "for"))
         return prevPreposition;
   }

   return result;
}

/// Split the base name after the last preposition, if there is one.
static bool splitBaseNameAfterLastPreposition(
   StringRef &baseName,
   StringRef &argName,
   const OmissionTypeName &paramType) {
   // Scan backwards for a preposition.
   auto nameWords = getWords(baseName);
   auto nameWordRevIterBegin = nameWords.rbegin(),
      nameWordRevIterEnd = nameWords.rend();

   // Find the last preposition.
   auto nameWordRevIter = findLastPreposition(nameWordRevIterBegin,
                                              nameWordRevIterEnd);

   if (nameWordRevIter == nameWordRevIterEnd) return false;

   // We found a split point.
   auto preposition = *nameWordRevIter;

   // If we have a conflict with the word before the preposition, don't
   // split.
   if (std::next(nameWordRevIter) != nameWordRevIterEnd &&
       wordConflictsBeforePreposition(*std::next(nameWordRevIter), preposition))
      return false;

   // If we have a conflict with the word after the preposition, don't
   // split.
   if (nameWordRevIter != nameWordRevIterBegin &&
       wordConflictsAfterPreposition(*std::prev(nameWordRevIter), preposition))
      return false;

   // If the word preceding the preposition extends the preposition, it
   // will never be dropped.
   if (std::next(nameWordRevIter) != nameWordRevIterEnd &&
       priorWordExtendsPreposition(*std::next(nameWordRevIter), preposition)) {
      ++nameWordRevIter;
      preposition = StringRef((*nameWordRevIter).begin(),
                              preposition.size() + (*nameWordRevIter).size());
   }

   // Determine whether we should drop the preposition.
   StringRef beforePreposition(baseName.begin(),
                               preposition.begin() - baseName.begin());
   StringRef afterPreposition(preposition.end(),
                              baseName.end() - preposition.end());
   bool dropPreposition = isVacuousPreposition(beforePreposition,
                                               preposition,
                                               afterPreposition,
                                               paramType);

   // By default, put the preposition on the argument label.
   bool prepositionOnArgLabel =
      shouldPlacePrepositionOnArgLabel(beforePreposition, preposition,
                                       afterPreposition);
   if (prepositionOnArgLabel)
      ++nameWordRevIter;

   unsigned startOfArgumentLabel = nameWordRevIter.base().getPosition();
   unsigned endOfBaseName = startOfArgumentLabel;

   // If we're supposed to drop the preposition, do so.
   if (dropPreposition) {
      if (prepositionOnArgLabel)
         startOfArgumentLabel += preposition.size();
      else {
         endOfBaseName -= preposition.size();
      }
   }
   if (endOfBaseName == 0) return false;

   // If the base name is vacuous or is a keyword and there are two or
   // fewer words in the base name, don't split.
   auto newBaseName = baseName.substr(0, endOfBaseName);
   {
      auto newWords = getWords(newBaseName);
      auto newWordsIter = newWords.begin();
      bool isKeyword = !canBeMemberName(*newWordsIter);
      bool isVacuous = isVacuousName(*newWordsIter);
      if (isKeyword || isVacuous) {
         // Just one word?
         ++newWordsIter;
         if (newWordsIter == newWords.end()) return false;

         // Or two words, if it's vacuous.
         ++newWordsIter;
         if (newWordsIter == newWords.end() && isVacuous) return false;

         // Okay: there is enough in the base name.
      }
   }

   // Update the argument label and base name.
   argName = baseName.substr(startOfArgumentLabel);
   baseName = newBaseName;

   return true;
}

/// Split the base name, if it makes sense.
static bool splitBaseName(StringRef &baseName, StringRef &argName,
                          const OmissionTypeName &paramType,
                          StringRef paramName) {
   // If there is already an argument label, do nothing.
   if (!argName.empty()) return false;

   // Try splitting a Boolean "Animated".
   if (paramType.isBoolean() &&
       getLastWord(baseName) == "Animated") {
      baseName = baseName.drop_back(strlen("Animated"));
      argName = "animated";
      return true;
   }

   // Don't split anything that starts with "set".
   if (getFirstWord(baseName) == "set")
      return false;

   // Don't split a method that looks like an action (with a "sender"
   // of type AnyObject).
   if (paramName == "sender" &&
       getLastWord(paramType.Name) == "Object")
      return false;

   // Try splitting after the last preposition.
   if (splitBaseNameAfterLastPreposition(baseName, argName, paramType))
      return true;

   return false;
}

bool omitNeedlessWords(StringRef &baseName,
                       MutableArrayRef<StringRef> argNames,
                       StringRef firstParamName,
                       OmissionTypeName givenResultType,
                       OmissionTypeName contextType,
                       ArrayRef<OmissionTypeName> paramTypes,
                       bool returnsSelf,
                       bool isProperty,
                       const InheritedNameSet *allPropertyNames,
                       StringScratchSpace &scratch) {
   bool anyChanges = false;
   OmissionTypeName resultType = returnsSelf ? contextType : givenResultType;

   /// Local function that lowercases all of the base names and
   /// argument names before returning.
   auto lowercaseAcronymsForReturn = [&] {
      StringRef newBaseName = toLowercaseInitialisms(baseName, scratch);
      if (baseName.data() != newBaseName.data()) {
         baseName = newBaseName;
         anyChanges = true;
      }

      for (StringRef &argName : argNames) {
         StringRef newArgName = toLowercaseInitialisms(argName, scratch);
         if (argName.data() != newArgName.data()) {
            argName = newArgName;
            anyChanges = true;
         }
      }

      return anyChanges;
   };

   // If the result type matches the context, remove the context type from the
   // prefix of the name.
   bool resultTypeMatchesContext = (resultType == contextType);
   if (resultTypeMatchesContext) {
      StringRef newBaseName = omitNeedlessWordsFromPrefix(baseName, contextType);
      if (newBaseName != baseName) {
         baseName = newBaseName;
         anyChanges = true;
      }
   }

   // Strip the context type from the base name of a method.
   if (!isProperty) {
      StringRef newBaseName = omitSelfTypeFromBaseName(baseName, contextType,
                                                       allPropertyNames, scratch);
      if (newBaseName != baseName) {
         baseName = newBaseName;
         anyChanges = true;
      }
   }

   if (paramTypes.empty()) {
      if (resultTypeMatchesContext) {
         StringRef newBaseName = omitTrailingTypeNameWithSpecialCases(
            baseName, resultType, NameRole::Property, allPropertyNames);
         if (newBaseName != baseName) {
            baseName = newBaseName;
            anyChanges = true;
         }
      }

      return lowercaseAcronymsForReturn();
   }

   if (getFirstWord(baseName) == "set") {
      StringRef newBaseName = omitTrailingTypeNameWithSpecialCases(
         baseName, contextType, NameRole::Property, allPropertyNames);
      if (newBaseName != baseName) {
         baseName = newBaseName;
         anyChanges = true;
      }
   }

   // If needed, split the base name.
   if (!argNames.empty() &&
       splitBaseName(baseName, argNames[0], paramTypes[0], firstParamName))
      anyChanges = true;

   // Omit needless words based on parameter types.
   for (unsigned i = 0, n = argNames.size(); i != n; ++i) {
      // If there is no corresponding parameter, there is nothing to
      // omit.
      if (i >= paramTypes.size()) continue;

      // Omit needless words based on the type of the parameter.
      NameRole role = i > 0 ? NameRole::SubsequentParameter
                            : argNames[0].empty() ? NameRole::BaseName
                                                  : baseName == "init" ? NameRole::SubsequentParameter
                                                                       : paramTypes[0].hasDefaultArgument()
                                                                         ? NameRole::SubsequentParameter
                                                                         : NameRole::FirstParameter;

      // Omit needless words from the name.
      StringRef name = role == NameRole::BaseName ? baseName : argNames[i];
      StringRef newName = omitTrailingTypeNameWithSpecialCases(
         name, paramTypes[i], role,
         role == NameRole::BaseName ? allPropertyNames : nullptr);

      if (name == newName) continue;

      // Record this change.
      anyChanges = true;
      if (role == NameRole::BaseName) {
         baseName = newName;
      } else {
         argNames[i] = newName;
      }
   }

   return lowercaseAcronymsForReturn();
}

} // polar